Search engine systems typically perform a search operation that can compare a search key value (e.g., a comparand) against a number of other data values. In the event a search key value matches a data value, a search key result may be considered a “hit” (e.g., match). If a search key value does not match any data values, a search result may be considered a “miss” (e.g., no match). Search engine systems continue to gain prevalence in networking hardware, and the like, as packet processing can require rapid matching of header fields to various tables in order to execute various functions on data packets. Such functions can include packet forwarding, filtering, or other types of processing.
While search engines can be based on a general-purpose processor and an accompanying algorithm, such approaches may be undesirably costly or slower in speed when compared to systems based on devices that may specialize in more rapid matching capabilities. One such device is a content addressable memory (CAM) device.
A CAM based search engine can typically include one or more CAM devices. A CAM device may include a number of entries, each of which may store a data value, or portion thereof. In a search operation, a comparand (or key) may be compared to multiple entries to see if all, or a portion, of the key matches an entry. After a search operation, a CAM device may give a search result as an output. Typically a search result may provide associated data directly, or can provide an “index” value that may be used to retrieve associated data from another device, such as a random access memory (RAM).
CAM devices may take a variety of forms. As but a few of the possible examples, a CAM device may be based on particular types of CAM cells. Such cells may include storage circuits integrated with compare circuits. Examples of storage circuits may be static random access memory (SRAM) type cells or dynamic random access memory (DRAM) type cells. Alternate approaches may include random access memories (RAM) arrays, or the like, with separate matching circuits and/or processing circuits.
A conventional CAM device and CAM based search engine device will now be described.
Referring to FIG. 19, a conventional CAM based device is set forth in a block diagram and designated by the general reference character 1900. A CAM device 1900 may include CAM entries 1902, an address decoder 1904, a compare data portion 1906, and a priority encoder 1908. CAM entries 1902 may store data values for comparison with a search key value. Address decoder 1904 may decode address values to provide access to CAM entries 1902. Compare data portion 1906 may apply search key values to CAM entries 1902. Priority encoder 1908 may prioritize match indications from CAM entries 1902, and encode a highest priority match entry into an index value.
The conventional CAM of FIG. 19 also includes a buffer 1910 and a command decoder 1912. A buffer 1910 may receive and output data values. In particular, a buffer 1910 may receive data values to be written into CAM entries 1902, search key values for application to CAM entries 1902, and output data values read from CAM entries 1902. A command decoder 1912 may receive command values and generate control signals from such command values for executing predetermined operations within CAM device 1900.
A conventional CAM device 1900 can also include dedicated input/outputs (I/Os) 1914-0, 1914-1 and 1914-2. Dedicated I/Os (1914-0, 1914-1 and 1914-2) may receive only predetermined values. Thus, in FIG. 19, dedicated I/Os 1914-0 may receive only address data or entry data, and may provide entry data. Similarly, dedicated I/Os 1914-1 may only receive command data, while dedicated I/Os 1914-2 may only provide index values. In a packaged CAM device, dedicated I/Os (1914-0, 1914-1 and 1914-2) can correspond to conductive leads of a package.
It is noted that conventional CAM devices may also include a RAM interface, or the like, for receiving index values. A RAM interface may generate address and control signals for a RAM device to thereby access data associated with a given index value.
A conventional CAM-based search engine system will now be described with reference to FIG. 20. The conventional CAM-based search engine system 2000 shown in FIG. 20 includes a command issuing device (“host”) 2002, a CAM device 2004, and a RAM device 2006. A command issuing device 2002 may provide command and search data to dedicated I/Os of a CAM device 2004. In response to such command and search data, a CAM device 2004 can generate index values. Such index values can be received by a RAM interface within a CAM device 2004, which can generate memory address and control signals ADD/CTRL in response thereto. Memory address and control signals ADD/CTRL may be received on dedicated I/Os of a RAM device 2006. From such memory address and control signals, a RAM device 2006 may provide associated data to a data bus 2008.
While conventional CAM devices and CAM-based search engines can typically provide a fast rate of search relative to processor systems, it is always a desirable goal to provide faster search rates.
It is also noted that the conventional CAM-based search engine system of FIG. 20 shows a system with relatively few components. However, as such systems scale up in size, there may be increased wiring and/or operational complexity. In particular, many CAM devices and/or RAM devices may operate according to some kind of enabling signal, or the like. For example, a CAM device may identify command data according to a command valid signal, or the like. Similarly, a RAM device can be enabled by a chip select signal, or the like. As component numbers are increased, the number of signal lines that carry such enabling signal can increase. Further, it can become increasingly difficult to match signal line impedances with respect to a host device. Consequently, a host may have to accommodate different timings between different devices.
In light of the above, it would be desirable to arrive at some way of increasing overall search rates for a CAM-based search engine relative to conventional approaches. In addition, or alternatively, it would be desirable to arrive at a CAM device configuration that results in more simplified wiring as the number of CAM devices in such a system is increased.